function maxNumber(nums1: number[], nums2: number[], k: number): number[] {
    const max = Math.min(nums1.length,k)
    const start = Math.max(0,k-nums2.length)    //保证开始的时候2的长度可以满足
    let ans:number[] = []
    for(let i=start;i<=max&&k-i>=0;i++){
        let s1 = getMaxSubSeq(nums1,i)
        let s2 = getMaxSubSeq(nums2,k-i)
        let merge = mergeSeq(s1,s2)
        if(compare(ans,merge)){
            ans = merge
        }
    }
    return ans
};

//获取长度为len的最大子序列
function getMaxSubSeq(nums:number[],len:number):number[]{
    if(len==4&&nums[0]==4){
        console.log(1)
    }
    let remove = 0
    let stack:number[] = []
    let top = -1
    let canRemove = nums.length-len
    nums.forEach(v=>{
        while(top>=0&&remove<canRemove&&stack[top]<v){
            top--
            stack.pop()
            remove++
        }
        if(top<len-1){
            stack.push(v)
            top++
        }else{
            remove++
        }
        
    })
    return stack
}


//合并两个子序列
function mergeSeq(s1:number[],s2:number[]):number[]{
    let i1 = 0
    let i2 = 0
    let merge:number[] = []
    while(i1<s1.length&&i2<s2.length){
        if(s1[i1]>s2[i2]){
            merge.push(s1[i1++])
        }else if(s2[i2]>s1[i1]){
            merge.push(s2[i2++])
        }else{
            let t1 = i1
            let t2 = i2
            while(t1<s1.length&&t2<s2.length&&s1[t1]==s2[t2]){
                t1++
                t2++
            }
            if(t2==s2.length||s1[t1]>s2[t2]){
                merge.push(s1[i1++])
            }else{
                merge.push(s2[i2++])
            }
        }
    }
    if(i1!=s1.length){
        merge.push(...s1.slice(i1))
    }else{
        merge.push(...s2.slice(i2))
    }
    return merge
}

//判断s1<s2
function compare(s1:number[],s2:number[]):boolean{
    for(let i=0;i<s1.length;i++){
        if(s1[i]<s2[i]) return true
        else if(s1[i]>s2[i]) return false
    }
    return true
}

console.log(maxNumber([7,6,1,9,3,2,3,1,1]
    ,[4,0,9,9,0,5,5,4,7]
    ,9))